package com.topcoder.srm513;

/**
 * Manao has a board filled with digits represented as String[] board. The j-th
 * character of the i-th element of board represents the digit written in cell
 * in row i, column j of the board. The rows are numbered from top to bottom and
 * the columns are numbered from left to right.
 * 
 * Manao is going to cut it into several non-overlapping fragments. Each of the
 * fragments will be a horizontal or vertical strip containing 1 or more
 * elements. A strip of length N can be interpreted as an N-digit number in base
 * 10 by concatenating the digits on the strip in order. The horizontal strips
 * are read from left to right and the vertical strips are read from top to
 * bottom. The picture below shows a possible cutting of a 4x4 board:
 * 
 * The sum of the numbers on the fragments in this picture is 493 + 7160 + 23 +
 * 58 + 9 + 45 + 91 = 7879.
 * 
 * Manao wants to cut the board in such a way that the sum of the numbers on the
 * resulting fragments is the maximum possible. Compute and return this sum.
 * 
 * [Algorithm]
 * Key point: first cut must be a cut-through.
 */
public class CutTheNumbers {

	String[] my;
	int[][][][] best = new int[4][4][4][4];

	private int dp(int a, int b, int c, int d) {
		if (best[a][b][c][d] != -1) {
			return best[a][b][c][d];
		}

		if (a == c) {// same row
			int tmp = 0;

			for (int i = b; i <= d; i++) {
				tmp *= 10;
				tmp += my[a].charAt(i) - '0';
			}

			return best[a][b][c][d] = tmp;
		}

		if (b == d) {
			int tmp = 0;

			for (int i = a; i <= c; i++) {
				tmp *= 10;
				tmp += my[i].charAt(d) - '0';
			}

			return best[a][b][c][d] = tmp;
		}

		// cur |
		int tmp = 0;
		for (int i = b; i < d; i++) {
			int v1 = dp(a, b, c, i);
			int v2 = dp(a, i + 1, c, d);

			if (v1 + v2 > tmp) {
				tmp = v1 + v2;
			}
		}

		// cut -
		for (int i = a; i < c; i++) {
			int v1 = dp(a, b, i, d);
			int v2 = dp(i + 1, b, c, d);

			if (v1 + v2 > tmp) {
				tmp = v1 + v2;
			}
		}

		return best[a][b][c][d] = tmp;
	}

	public int maximumSum(String[] board) {
		my = board;

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					for (int m = 0; m < 4; m++) {
						best[i][j][k][m] = -1;
					}
				}
			}
		}

		return dp(0, 0, board.length - 1, board[0].length() - 1);
	}
	
	/**
	 * Public Answer
	 */
	public int maximumSum0(String[] board) {
	    int w=board.length, h=board[0].length();
	    int t = w*h;
	    int res = 0;

	    // Use a bitmask to simulate finding all subsets of cells. Then use
	    // each subset to define which cell is marked as vertical or not.
	    for (int mask=0; mask<(1<<t); mask++) {
	        int s = 0;
	        // Calculate each column
	        for (int i=0; i<w; i++) {
	            int x = 0;
	            for (int j=0; j<h; j++) {
	                if ( (mask&(1<<(i*h+j)))==0 ) { //horizontal
	                    s += x;
	                    x = 0;
	                } else { // vertical
	                    x = x*10 + (int)(board[i].charAt(j)-'0');
	                }
	            }
	            s += x;
	        }
	        // Calculate each row
	        for (int j=0; j<h; j++) {
	            int x = 0;
	            for (int i=0; i<w; i++) {
	                if ( (mask&(1<<(i*h+j)))!=0 ) { //vertical
	                    s += x;
	                    x = 0;
	                } else { // horzizontal
	                    x = x*10 + (int)(board[i].charAt(j)-'0');
	                }
	            }
	            s += x;
	        }
	        // Remember the best sum found so far:
	        res = Math.max(res, s);
	    }
	    return res;
	}
}
